package root;

public class Three {
	public class EL
	{
		int num;
		EL left;
		EL right;
		EL iam;
		EL parent;
		
		public EL(int num, EL parent)
		{
			this.num = num;
			this.left = null;
			this.right = null;
			this.iam = this;
			this.parent = parent;
		}
	}
	
	EL root;
	int lenght;
	
	public void BinaryTree()
	{
		root = null;
		lenght = 0;		
	}
	
	public void BinaryTree(int num)
	{
		root = new EL(num, null);
		lenght = 1;
	}

	public EL add(int num)
	{
		lenght++;
		if(root == null)
		{
			root = new EL(num, null);
			return root; 
		}
		
		EL EL = root;
		while(EL != null)
			if(num >= EL.num)
				if(EL.right == null)
				{
					EL.right = new EL(num, EL);
					return EL.right;
				}
				else
					EL = EL.right;
			else if(num < EL.num)
				if(EL.left == null)
				{
					EL.left = new EL(num, EL);
					return EL.left;
				}
				else
					EL = EL.left;
		
		lenght--;
		return null;
	}
	
	public void printTree()
	{
		System.out.println("\nLenght: " + lenght);
		printTree(root, 0);
	}
	
	private void printTree(EL EL, int level)
	{
		 if(EL.right != null)
			 printTree(EL.right, level+1);
		 
		 for(int k = 0; k < level; k++)
			 System.out.print("\t");
		 System.out.println(EL.num);
		 
		 if(EL.left != null)
			 printTree(EL.left, level+1);
	}
	
	public EL search(int num)
	{
		EL minEL = root;
		EL maxEL = root;
		
		EL EL = root;
		while(EL != null)
			if(num == EL.num)
				return EL;
			else if(num > EL.num)
			{
				if(maxEL.num < EL.num)maxEL = EL;
				minEL = EL;
				EL = EL.right;
			}
			else if(num < EL.num)
			{
				if(minEL.num > EL.num)minEL = EL;
				maxEL = EL;
				EL = EL.left;
			}
		
		if(maxEL.num - num <= num - minEL.num)
			return maxEL;
		else
			return minEL;
	}

	public EL getMax()
	{
		EL EL = root;
		while(EL.right != null)
			EL = EL.right;
		return EL;
	}
		
	public EL getMin()
	{
		EL EL = root;
		while(EL.left != null)
			EL = EL.left;
		return EL;
	}

	public boolean remove(int num)
	{
		return remove(num, root);
	}
	
	private boolean remove(int num, EL EL)
	{
		while(EL != null)
		{
			if(num < EL.num)
				EL = EL.left;
			else if(num > EL.num)
				EL = EL.right;
			else if(num == EL.num)
			{
				if(EL.left != null && EL.right != null)
				{
					if(EL.right.left == null)
					{
						EL.right.left = EL.left;
						
						if(EL == root)
							root = EL.right;
						else if(EL.parent.left == EL)
							EL.parent.left = EL.right;
						else if(EL.parent.right == EL)
							EL.parent.right = EL.right;
						lenght--;
						return true;
					}
					else
					{
						EL ELLeft = EL.right.left;
						while(ELLeft.left != null)
							ELLeft = ELLeft.left;
						EL.num = ELLeft.num;
						return remove(ELLeft.num, ELLeft);
					}
				}
				else	
				{
					if(EL.left == null && EL.right == null)
					{
						if(EL == root)
							root = null;
						else if(EL.parent.left == EL)
							EL.parent.left = null;
						else if(EL.parent.right == EL)
							EL.parent.right = null;
					}
					else if(EL.left != null)
					{
						if(EL == root)
							root = EL.left;
						else if(EL.parent.left == EL)
							EL.parent.left = EL.left;
						else if(EL.parent.right == EL)
							EL.parent.right = EL.left;
					}
					else if(EL.right != null)
					{
						if(EL == root)
							root = EL.right;
						else if(EL.parent.left == EL)
							EL.parent.left = EL.right;
						else if(EL.parent.right == EL)
							EL.parent.right = EL.right;
					}
					lenght--;
					return true;
				}
			}
		}
		return false;
	}
	
}
